/*
 * @Author: szx
 * @Date: 2022-04-29 13:33:12
 * @LastEditTime: 2022-04-29 13:56:08
 * @Description:
 * @FilePath: \leetcode\400-499\427\427.js
 */
function Node(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight) {
    this.val = val;
    this.isLeaf = isLeaf;
    this.topLeft = topLeft;
    this.topRight = topRight;
    this.bottomLeft = bottomLeft;
    this.bottomRight = bottomRight;
}

/**
 * @param {number[][]} grid
 * @return {Node}
 */
var construct = function (grid) {
    const n = grid.length;
    function dfs(i0, i1, j0, j1) {
        if (i0 === i1 && j0 === j1) return new Node(grid[i0][j0], true);
        // 递归求出4个子节点
        const mi = Math.floor(i1 / 2 + i0 / 2),
            mj = Math.floor(j1 / 2 + j0 / 2);
        const tl = dfs(i0, mi, j0, mj);
        const tr = dfs(i0, mi, mj + 1, j1);
        const bl = dfs(mi + 1, i1, j0, mj);
        const br = dfs(mi + 1, i1, mj + 1, j1);
        const children = [tl, tr, bl, br];
        // 求出所有子节点的 val 之和
        const val = children.reduce((a, c) => a + c.val, 0);
        // isLeaf：所有子节点的 val 之和是 4 或 0，且所有子节点都是叶子节点
        const isLeaf = val % 4 === 0 && children.every((n) => n.isLeaf);
        // node.val：所有子节点的 val 之和除以 4 并向上取整
        // node.isLeaf：所有子节点的 val 之和是 4 或 0，且所有子节点都是叶子节点
        // 4个子节点：当前节点是否有子节点由 isLeaf 决定
        return new Node(Math.ceil(val / 4), isLeaf, ...(isLeaf ? [] : children));
    }
    return dfs(0, n - 1, 0, n - 1);
};
